package Datas_Structure.Tree;

/**
 * 二叉排序树（BST）
 * 对于二叉树中任何一个的非叶子节点，它的左子树比当前节点小，它的右子树比当前节点大（空树也是）
 */

/**
 * 树
 */
public class BinarySortTree {
    Node root;

    /**
     * 向二叉排序树中添加节点
     */
    public void add(Node node) {
        //如果是一棵空树
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    /**
     * 中序遍历二叉排序树
     */
    public void midShow() {
        if (root != null) {
            root.midShow(root);
        }
    }
    /**
     * 查找一个节点
     */
    public Node search(int value){
        if (root == null){
            return null;
        }else {
            return root.search(value);
        }
    }
}

/**
 * 节点
 */
class Node {
    int value;
    Node Rnode;
    Node Lnode;

    public Node(int value) {
        this.value = value;
    }

    /**
     * 向子树中添加节点
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        //判断当前节点和传入节点的大小
        //添加的节点比当前节点的值更小
        if (node.value < this.value) {
            //如果左节点为空
            if (this.Lnode == null) {
                this.Lnode = node;
            } else {
                this.Lnode.add(node);
            }
        } else {
            //如果右节点为空
            if (this.Rnode == null) {
                this.Rnode = node;
            } else {
                this.Rnode.add(node);
            }
        }

    }

    /**
     * 中序遍历
     *
     * @param node
     */
    public void midShow(Node node) {
        if (node == null) {
           return;
        }
        midShow(node.Lnode);
        System.out.print(node.value + " ");
        midShow(node.Rnode);
    }

    /**
     * 查找一个节点
     * @param value
     * @return
     */
    public Node search(int value) {
        //如果是当前值则返回当前值
      if(this.value == value){
          return this;
      }else if (this.value > value){
              //如果为空则返回
              if (Lnode == null ){
                  return null;
              }
              //否则继续调用函数
            return Lnode.search(value);
          }else {
              if (Rnode == null){
                  return null;
              }
             return Rnode.search(value);
          }
      }
    }

class BinaryTest{
    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9};
        //创建一颗二叉树
        BinarySortTree binarySeachTree = new BinarySortTree();
        //添加元素
        for (int i : arr) {
            binarySeachTree.add(new Node(i));
        }
        //遍历节点
        binarySeachTree.midShow();
        //查找节点
        System.out.println(binarySeachTree.search(10).value);
        System.out.println(binarySeachTree.search(20));
    }
}